package com.example.leetcode;

public class FindLowestCommonAncestor {
    public static class Node {
        public int data;
        public Node left;
        public Node right;

        public Node(int data) {
            this.data = data;
        }
    }

    public static Node getLowestAncestor(Node root, Node n1, Node n2) {
        if (root == null || root == n1 || root == n2) {
            return root;
        }
        Node left = getLowestAncestor(root.left, n1, n2);
//        循环也走上一步
        Node right = getLowestAncestor(root.right, n1, n2);
        if (left != null && right != null) {
            return root;
        }
        return left != null ? left : right;
    }

    public static void main(String[] args) {
        Node node1 = new Node(3);
        Node node2 = new Node(5);
        Node node3 = new Node(1);
        Node node4 = new Node(6);
        Node node5 = new Node(2);
        Node node6 = new Node(0);
        Node node7 = new Node(8);
        node1.left = node2;
        node1.right = node3;
        node2.left = node4;
        node2.right = node5;
        node3.left = node6;
        node3.right = node7;
        Node n = getLowestAncestor(node1, node4, node7);
        System.out.printf("The lowest common ancestor is: %d", n.data);
    }

}
